home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Caml Light 0.61 / Source / src / lib / hashtbl.mli < prev    next >
Encoding:
Text File  |  1993-09-24  |  3.2 KB  |  70 lines  |  [TEXT/MPS ]
  1. (* Hash tables and hash functions *)
  2.  
  3. (* Hash tables are hashed association tables, with in-place modification. *)
  4.  
  5. type ('a, 'b) t mutable;;
  6.         (* The type of hash tables from type ['a] to type ['b]. *)
  7.  
  8. value new : int -> ('a,'b) t
  9.         (* [new n] creates a new, empty hash table, with initial size [n].
  10.            The table grows as needed, so [n] is just an initial guess.
  11.            Better results are said to be achieved when [n] is a prime
  12.            number. *)
  13.  
  14.   and clear : ('a, 'b) t -> unit
  15.         (* Empty a hash table. *)
  16.  
  17.   and add : ('a, 'b) t -> 'a -> 'b -> unit
  18.         (* [add tbl x y] adds a binding of [x] to [y] in table [tbl].
  19.            Previous bindings for [x] are not removed, but simply
  20.            hidden. That is, after performing [remove tbl x], the previous
  21.            binding for [x], if any, is restored.
  22.            (This is the semantics of association lists.) *)
  23.  
  24.   and find : ('a, 'b) t -> 'a -> 'b
  25.         (* [find tbl x] returns the current binding of [x] in [tbl],
  26.            or raises [Not_found] if no such binding exists. *)
  27.  
  28.   and find_all : ('a, 'b) t -> 'a -> 'b list
  29.         (* [find_all tbl x] returns the list of all data associated with [x]
  30.            in [tbl]. The current binding is returned first, then the previous
  31.            bindings, in reverse order of introduction in the table. *)
  32.  
  33.   and remove : ('a, 'b) t -> 'a -> unit
  34.         (* [remove tbl x] removes the current binding of [x] in [tbl],
  35.            restoring the previous binding if it exists.
  36.            It does nothing if [x] is not bound in [tbl]. *)
  37.  
  38.   and do_table : ('a -> 'b -> 'c) -> ('a, 'b) t -> unit
  39.         (* [do_table f tbl] applies [f] to all bindings in table [tbl],
  40.        discarding all the results.
  41.            [f] receives the key as first argument, and the associated value
  42.            as second argument. The order in which the bindings are passed to
  43.            [f] is unpredictable. The same binding
  44.            can be presented several times to [f]. *)
  45. ;;
  46.  
  47. (*** The polymorphic hash primitive *)
  48.  
  49. value hash : 'a -> int
  50.         (* [hash x] associates a positive integer to any value of
  51.            any type. It is guaranteed that
  52.                 if [x = y], then [hash x = hash y]. 
  53.            Moreover, [hash] always terminates, even on cyclic
  54.            structures. *)
  55. ;;
  56. value hash_param : int -> int -> 'a -> int = 3 "hash_univ_param"
  57.         (* [hash_param n m x] computes a hash value for [x], with the
  58.            same properties as for [hash]. The two extra parameters [n] and
  59.            [m] give more precise control over hashing. Hashing performs a
  60.            depth-first, right-to-left traversal of the structure [x], stopping
  61.            after [n] meaningful nodes were encountered, or [m] nodes,
  62.            meaningful or not, were encountered. Meaningful nodes are: integers;
  63.            floating-point numbers; strings; characters; booleans; and constant
  64.            constructors. Larger values of [m] and [n] means that more
  65.            nodes are taken into account to compute the final hash
  66.            value, and therefore collisions are less likely to happen.
  67.            However, hashing takes longer. The parameters [m] and [n]
  68.            govern the tradeoff between accuracy and speed. *)
  69. ;;
  70.